#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
class Solution {
public:
	int networkDelayTime(vector<vector<int>>& times, int n, int k) {
		vector<vector<pii>> adjacencyList(n + 1, vector<pii> {});
		for (auto& time : times) adjacencyList[time[0]].emplace_back(time[1], time[2]);

		vector<bool> vis(n + 1, false);
		vector<int> minDis(n + 1, INT_MAX); minDis[0] = -1; minDis[k] = 0;
		for (auto [e, w] : adjacencyList[k]) minDis[e] = w;

		/* 每次选取一个最短距离&&未访问点更新全部距离 */
		for (int i = 1, len = n + 1; i < len; i++) {
			int minIdx = -1, minD = INT_MAX;
			/* 找出最小距离 && 未访问过的点 */
			for (int j = 1; j < len; j++) {
				if (vis[j]) continue;
				if (minDis[j] < minD) {
					minD = minDis[j];
					minIdx = j;
				}
			}
			if (minIdx == -1) break;
			for (auto [e, w] : adjacencyList[minIdx]) minDis[e] = min(minDis[e], w + minD);
			vis[minIdx] = true;
		}

		int res = *max_element(minDis.begin(), minDis.end());
		return res == INT_MAX? -1: res;
	}

private:
};

int main()
{
	Solution solution;
	return 0;
}
